package com.xx.springboot.DataStructure.LeetCode.BST;

import java.util.LinkedList;
import java.util.Queue;

/**
     给定一个二叉树，检查它是否是镜像对称的。

     例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

     1
     / \
     2   2
     / \ / \
     3  4 4  3
     但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

     1
     / \
     2   2
     \   \
     3    3
     说明:

     如果你可以运用递归和迭代两种方法解决这个问题，会很加分。
 */
public class isSymmetric {


    /**
     * 使用队列的方式求解
     * @param root
     * @return
     */
    public boolean isSymmetric(TreeNode root){
        if(root == null)
            return true;

        /**
         * 将元素入队
         */
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root.left);
        q.add(root.right);

        while (!q.isEmpty()) {
            TreeNode left = q.poll();
            TreeNode right = q.poll();

            /**
             * 取出元素判断是否满足条件
             */
            if(left == null && right == null)
                continue;
            if(left == null || right == null)
                return false;
            if(left.val != right.val)
                return false;

            /**
             * 判断之后 将当前两个节点的子元素 添加到队列中
             */

            q.add(left.left);
            q.add(right.right);
            q.add(left.right);
            q.add(right.left);
        }
        return true;
    }



    /**
     * 使用递归的方式求解
     * @param root
     * @return
     */
    public boolean isSymmetric1(TreeNode root) {
        if(root == null)
            return true;
        return compareNode(root.left, root.right);
    }

    public boolean compareNode(TreeNode root1, TreeNode root2) {
        if(root1 == null && root2 == null)
            return true;
        if(root1 == null || root2 == null)
            return false;
        if(root1.val != root2.val)
            return false;

        return compareNode(root1.left, root2.right) && compareNode(root1.right, root2.left);
    }

}
